import bisect
import heapq
import itertools
import math
from collections import defaultdict, deque
from functools import reduce
from heapq import heappop, heappush
from math import isqrt, inf
from operator import or_, xor

from .data_struct import *
from .method import *


def solution_2706(prices: List[int], money: int) -> int:
    min_1 = prices[0] if prices[0] <= prices[1] else prices[1]
    min_2 = prices[1] if prices[0] <= prices[1] else prices[0]
    for price in prices[2:]:
        if price < min_1:
            min_2 = min_1
            min_1 = price
        elif min_1 <= price < min_2:
            min_2 = price
    res = money - min_1 - min_2
    return money if res < 0 else res


def solution_2807(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    p, q = head, head.next
    while p and q:
        tmp = gcd_euclid(p.val, q.val)
        p.next = ListNode(tmp)
        p.next.next = q
        p = q
        q = q.next
    return head


def solution_2707(s: str, dictionary: List[str]) -> int:
    """
    设 n 是 s 的长度，现在有两种基本的分割方案：

    把 s 的最后一个字符 s[n−1] 当做是额外字符，那么问题转为长度为 n−1 的子问题。
    找到一个 j 使得 s 的后缀 s[j...n−1] 构成的子串在 dictionary，那么问题转为长度为 j 的子问题。
    因此，定义 d[i] 为 sss 前缀 s[0...i−1] 的子问题，那么 d[i] 取下面两种情况的最小值：
    1. 把 s[i−1]当做是额外字符，d[i]=d[i−1]+1
    2. 遍历所有的 j(j∈[0,i−1])，如果子字符串 s[j...i−1]存在于 dictionary 中，那么 d[i]=mind[j]

    初始状态 d[0]=0d[0] = 0d[0]=0，最终答案为 d[n]d[n]d[n]。
    查找子串 s[j...i−1]s[j...i-1]s[j...i−1] 是否存在于 dictionary 可以使用哈希表。
    另外在实现动态规划时，可以使用记忆化搜索，也可以使用递推，这两种方式在时空复杂度方面并没有明显差异。
    """
    n = len(s)
    dp = [0] * (n + 1)  # dp[i]代表s[0:i]
    trie = Trie()
    for tmp in dictionary:
        trie.insert(tmp[::-1])
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + 1
        node = trie
        for j in range(i - 1, -1, -1):  # 逆序遍历i-1到0
            node, ok = track(node, s[j])
            if ok:
                dp[i] = min(dp[i], dp[j])
    return dp[n]


def solution_2696(s: str) -> int:
    stack = []
    for ch in s:
        if not stack:
            stack.append(ch)
        elif (ch == 'B' and stack[-1] == 'A') or (ch == 'D' and stack[-1] == 'C'):
            stack.pop()
        else:
            stack.append(ch)
    return len(stack)


def solution_2645(word: str) -> int:
    p, q, count = 0, 0, 0
    pattern = 'abc'
    while p < len(word):
        if word[p] != pattern[q]:
            count += 1
        else:
            p += 1
        q = (q + 1) % 3
    count += (3 - q) % 3
    return count


def solution_2645_2(word: str) -> int:
    # dp
    # d[i] = min(d[i]+2, d[i-1] -1)
    # 第二种情况需要word[i-1] > word[i-2],也就是word[i]是排在word[i-1]后面的字母,从而构成abc串
    n = len(word)
    d = [0] * (n + 1)
    d[1] = d[0] + 2
    for i in range(2, n + 1):
        d[i] = d[i - 1] + 2
        if word[i - 1] > word[i - 2]:
            d[i] = d[i - 1] - 1
    return d[n]


def solution_2645_3(word: str) -> int:
    # 直接拼接
    # 两个相邻位置之间插入字符数量
    # (word[i] - word[i-1] -1 + 3) mod 3
    # 头尾额外处理
    n = len(word)
    # word[0] 前 word[0]- 'a'
    # word[n-1]后 'c' - word[n-1]
    count = ord(word[0]) - ord(word[n - 1]) + 2
    for i in range(1, n):
        count += (ord(word[i]) - ord(word[i - 1]) + 2) % 3
    return count


def solution_2645_4(word: str) -> int:
    # 直接计算
    # 最终组数等于所有满足后者字符小于等于前者字符的情况+1
    n = len(word)
    count = 1
    for i in range(1, n):
        if word[i] <= word[i - 1]:
            count += 1
    return count * 3 - n


def solution_2719(num1: str, num2: str, min_sum: int, max_sum: int) -> int:
    # 超时
    # def get_sum(tmp: int) -> int:
    #     count = 0
    #     while tmp > 0:
    #         count += tmp % 10
    #         tmp = tmp // 10
    #     return count
    #
    # # f(num2, min_sum, max_sum) - f(num-1, min_sum, max_sum)
    # n1 = int(num1)
    # n2 = int(num2)
    # count_dp = 0
    # for i in range(0, n1):
    #     cur = get_sum(i)
    #     if min_sum <= cur <= max_sum:
    #         count_dp += 1
    # count_n1 = count_dp
    # for i in range(n1, n2 + 1):
    #     cur = get_sum(i)
    #     if min_sum <= cur <= max_sum:
    #         count_dp += 1
    # return (count_dp-count_n1) % 1000000007
    # 数位DP
    # d[][]表示还剩第i位到第0位的数字未填，而已填的数字位数之和为j时，符合条件的数字有多少个
    # d[0][j]表示还剩第0位的数字未填，而已填的数字位数之和为j时，符合条件的数字有多少个
    # 显然d[0][j]取决于第0位加上j的值是否满足条件，那么取值范围是0-10
    # d的记忆化过程是从i=0开始，i变大，j变小，但是每个状态只会计算一次
    N, M = 23, 401  # 限定d的空间大小
    MOD = 10 ** 9 + 7
    d = [[-1] * M for _ in range(N)]  # 预定义默认值

    def dfs(num, i, j, limit) -> int:
        if j > max_sum:  # 剪枝，如果j已经比max_sum大了，可以排除
            return 0
        if i == -1:  # 如果i遍历到-1，说明数字已经检查完了，j如果大于min_sum就可以记为1个有效的数字
            return j >= min_sum
        if not limit and d[i][j] != -1:  # 如果不是limit数，且已经存储了结果，那么返回对应的数即可
            return d[i][j]
        res = 0
        up = ord(num[i]) - ord('0') if limit > 0 else 9
        for x in range(up + 1):
            res = (res + dfs(num, i - 1, j + x, limit and x == up)) % MOD
        if not limit:
            d[i][j] = res
        return res

    def get(num):
        num = num[::-1]  # 题解判断方案是高位开始到低位，因此反转数字，使得n-1位对应d[n-1]
        return dfs(num, len(num) - 1, 0, True)

    # 简单得到num1-1
    def sub(num):
        i = len(num) - 1
        arr = list(num)
        while arr[i] == '0':
            i -= 1
        arr[i] = chr(ord(arr[i]) - 1)
        i += 1
        while i < len(num):
            arr[i] = '9'
            i += 1
        return ''.join(arr)

    return (get(num2) - get(sub(num1)) + MOD) % MOD


def solution_2744(words: List[str]) -> int:
    my_set = set(words)
    count = 0
    for word in words:
        if word[::-1] == word:
            continue
        if word[::-1] in my_set:
            count += 1
    return count // 2


def solution_2744_2(words: List[str]) -> int:
    # 只遍历一次
    my_set = set()
    count = 0
    for word in words:
        if word in my_set:
            count += 1
        my_set.add(word[::-1])
    return count


def solution_2809(nums1: List[int], nums2: List[int], x: int) -> int:
    def my_sort(left: int, right: int):
        if left >= right:
            return
        tmp = nums2[left]
        tmp1 = nums1[left]
        i = left
        j = right
        while i < j:
            while i < j and nums2[j] >= tmp:
                j -= 1
            nums2[i] = nums2[j]
            nums1[i] = nums1[j]
            while i < j and nums2[i] <= tmp:
                i += 1
            nums2[j] = nums2[i]
            nums1[j] = nums1[i]
        nums2[i] = tmp
        nums1[i] = tmp1
        my_sort(left, i - 1)
        my_sort(i + 1, right)

    n = len(nums1)
    my_sort(0, n - 1)
    # dp[i][j]:对前i个元素进行j次操作,所能减少的total的值
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    # sum = sum(nums1)+sum(nums2)*t-dp[n][t]
    # dp[i][j] = max(dp[i-1][j] , dp[i-1][j-1]+nums1[i-1]+nums2[i-1]*j)
    # 做操作肯定比不做要小
    sum1 = sum(nums1)
    sum2 = sum(nums2)
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + nums1[i - 1] + nums2[i - 1] * j)
        # 不能在循环里判断
        # dp[i][i]只是移除了所有前i个元素,并不是最小的值
        # 最小值可能存在于移除其他元素,但只用了i次
        # 因此要在遍历结束后再找答案
    for i in range(0, n + 1):
        if sum2 * i + sum1 - dp[n][i] <= x:
            return i
    return -1


def solution_2788(words: List[str], separator: str) -> List[str]:
    res = []
    for word in words:
        wl = word.split(separator)
        for w in wl:
            if len(w) > 0:
                res.append(w)
    return res


def solution_2788_2(words: List[str], separator: str) -> List[str]:
    res = []
    for word in words:
        last = 0
        for i in range(len(word)):
            if word[i] == separator:
                if i != last:
                    res.append(word[last:i])
                last = i + 1
        if last < len(word):
            res.append(word[last:])
    return res


def solution_2765(nums: List[int]) -> int:
    p, q = 0, 1
    cnt = 0
    max_cnt = 0
    while p < len(nums) and q < len(nums):
        if nums[q] - nums[p] == 1:
            cnt += 1
        else:
            max_cnt = max(max_cnt, cnt)
            if p > q:
                p, q = q, p
            if nums[q] - nums[p] == 1:
                cnt = 1
            else:
                cnt = 0
                p += 1
                q += 1
                continue
        if q < p:
            q += 2
        else:
            p += 2
    max_cnt = max(max_cnt, cnt)
    if max_cnt < 1:
        return -1
    else:
        return max_cnt + 1


def solution_2765_2(nums: List[int]) -> int:
    ans = -1
    i, n = 0, len(nums)
    while i < n - 1:
        if nums[i + 1] - nums[i] != 1:
            i += 1
            continue
        i0 = i
        i += 2
        while i < n and nums[i] == nums[i0] + (i - i0) % 2:
            i += 1
        ans = max(ans, i - i0)
        i -= 1  # 末尾有数重叠 3434 4545 4重叠
    return ans


def solution_2865(maxHeights: List[int]) -> int:
    n = len(maxHeights)
    heights = [0] * n
    sum_height = 0
    for i in range(n):
        cur_height = maxHeights[i]
        heights[i] = cur_height
        for j in range(i - 1, -1, -1):
            cur_height = min(maxHeights[j], cur_height)
            heights[j] = cur_height
        cur_height = heights[i]
        for k in range(i + 1, n):
            cur_height = min(maxHeights[k], cur_height)
            heights[k] = cur_height
        sum_height = max(sum_height, sum(heights))
    return sum_height


def solution_2865_2(maxHeights: List[int]) -> int:
    """
    单调栈的思路:
    先不考虑i在什么位置,用单调栈的思想遍历maxHeights,求得suf或者pre
    再从另一个方向走一遍,这一遍记录pre+suf,并逐渐更新答案
    """
    n = len(maxHeights)
    suf = [0] * (n + 1)  # 注意长度,额外的0表示最右边的塔最高
    stack = [n]  # 放一个哨兵节点,减少边界判断
    sum = 0  # 维护一个sum
    for i in range(n - 1, -1, -1):
        while len(stack) > 1 and maxHeights[i] <= maxHeights[stack[-1]]:  # 峰顶右侧离峰顶近的高度比远的小,那么弹出
            j = stack.pop()
            sum -= maxHeights[j] * (stack[-1] - j)  # 这一部分原本都是maxHeights[j],现在要更新成更小的值了
        sum += maxHeights[i] * (stack[-1] - i)  # 哨兵保证这里的stack[-1] - i是有意义的
        suf[i] = sum
        stack.append(i)  # 入栈
    ans = 0
    stack = [-1]
    sum = 0
    for i in range(n):
        while len(stack) > 1 and maxHeights[i] <= maxHeights[stack[-1]]:
            j = stack.pop()
            sum -= maxHeights[j] * (j - stack[-1])
        sum += maxHeights[i] * (i - stack[-1])
        ans = max(ans, sum + suf[i + 1])
        stack.append(i)
    return ans


def solution_2859(nums: List[int], k: int) -> int:
    n = len(nums)
    indexes = []
    # min_k = (1 << k) - 1
    tmp, cnt = n, 0
    while tmp > 0:
        cnt += 1
        tmp >>= 1
    comb = itertools.combinations(range(cnt + 1), k)
    for c in comb:
        index = 0
        for i in c:
            index += 1 << i
        if index < n:
            indexes.append(index)
    return sum([nums[x] for x in indexes])


def solution_2859_2(nums: List[int], k: int) -> int:
    # gospers_hack
    if k == 0:
        return nums[0]
    n = len(nums)
    tmp, cnt = n, 0
    while tmp > 0:
        cnt += 1
        tmp >>= 1
    # comb = itertools.combinations(range(cnt + 1), k)
    comb = []
    cur = (1 << k) - 1
    limit = 1 << cnt
    while cur < limit:
        comb.append(cur)
        lb = cur & -cur
        r = cur + lb
        cur = ((r ^ cur) >> ((lb & -lb).bit_length() - 1) + 2) | r
    return sum([nums[x] for x in comb if x < n])


def solution_2859_3(nums: List[int], k: int) -> int:
    # pop_count
    ans = 0
    for i in range(len(nums)):
        if pop_count(i) == k:
            ans += nums[i]
    return ans


def solution_2846(n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
    m = n.bit_length()
    g = [[] for _ in range(n)]
    for x, y, w in edges:
        g[x].append([y, w])
        g[y].append([x, w])
    freq = [[0] * 27 for _ in range(n)]
    depth = [0] * n
    pa = [[-1] * m for _ in range(n)]

    def dfs(n, p):
        pa[n][0] = p
        depth[n] = depth[p] + 1
        for y, w in g[n]:
            if y != p:
                # freq[y][w] += freq[n][w] + 1
                for k in range(27):
                    if k == w:
                        freq[y][w] = freq[n][w] + 1
                    else:
                        freq[y][k] = freq[n][k]
                dfs(y, n)

    dfs(0, -1)
    for i in range(m - 1):
        for x in range(n):
            if (p := pa[x][i]) != -1:
                pa[x][i + 1] = pa[p][i]

    def get_kth(x, k):
        for i in range(k.bit_length()):
            if (k >> i) & 1:
                x = pa[x][i]
                if x < 0:
                    return x
        return x

    res = []
    for x1, y1 in queries:
        x, y = x1, y1
        if depth[x] > depth[y]:
            x, y = y, x
        y = get_kth(y, depth[y] - depth[x])
        if x != y:
            for i in range(len(pa[x]) - 1, -1, -1):
                px, py = pa[x][i], pa[y][i]
                if px != py:
                    x, y = px, py
            lca = pa[x][0]
        else:
            lca = x
        max_freq, index = 0, 0
        for i in range(27):
            if max_freq < (f := freq[x1][i] + freq[y1][i] - freq[lca][i] * 2):
                max_freq = f
        res.append((sum(freq[x1]) + sum(freq[y1]) - sum(freq[lca]) * 2) - max_freq)
    return res


def solution_2861(n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
    ans = 0
    mx = min(stock) + budget  # 假设每个金属只要1个，价格也是1，因此上界是min(stock)+budget

    def check(num: int, comp: List[int]) -> bool:
        money = 0
        for s, base, c in zip(stock, comp, cost):
            if s < base * num:
                money += (base * num - s) * c  # 库存不够
                if money > budget:
                    return False
        return True

    for comp in composition:
        low = ans  # 如果一份都造不出来，那么就还是ans
        high = mx + 1
        while low + 1 < high:
            mid = (low + high) // 2
            if check(mid, comp):
                low = mid
            else:
                high = mid
        ans = low
    return ans


def solution_2808(nums: List[int]) -> int:
    """
    超时
    """
    my_set = set(nums)
    n = len(nums)
    min_cnt = 10 ** 5
    for num in my_set:
        ns_indexes = set()
        num_indexes = set()
        for i in range(len(nums)):
            if nums[i] == num:
                num_indexes.add(i)
            else:
                ns_indexes.add(i)
        cnt = 0
        while True:
            if len(ns_indexes) == 0:
                break
            tmp = []
            for num_index in num_indexes:
                p1, p2 = (num_index + 1) % n, (num_index - 1 + n) % n
                if p1 in ns_indexes:
                    ns_indexes.remove(p1)
                    tmp.append(p1)
                if p2 in ns_indexes:
                    ns_indexes.remove(p2)
                    tmp.append(p2)
            for t in tmp:
                num_indexes.add(t)
            cnt += 1
        min_cnt = min(min_cnt, cnt)
    return min_cnt


def solution_2808_2(nums: List[int]) -> int:
    """
    超时
    """
    my_set = set(nums)
    n = len(nums)
    min_cnt = 10 ** 5
    for num in my_set:
        tmp = []
        for i in range(len(nums)):
            if nums[i] == num:
                tmp.append(i)
        # 记录所有端点
        # 端点(i,j)之间变为x的时间为(j-i//2)
        cnt = 0
        for i in range(len(tmp) - 1):
            cnt = max(cnt, (tmp[i + 1] - tmp[i]) // 2)
        # n-2 到 2 之间为 n-1,0,1需要2次
        # (n-j+i)//2
        cnt = max(cnt, (n - tmp[-1] + tmp[0]) // 2)
        min_cnt = min(min_cnt, cnt)
    return min_cnt


def solution_2808_3(nums: List[int]) -> int:
    """
    和上面没差多少
    一些细节的优化
    """
    mp = defaultdict(list)
    res = n = len(nums)
    for i, a in enumerate(nums):
        mp[a].append(i)
    for pos in mp.values():
        mx = pos[0] + n - pos[-1]
        for i in range(len(pos) - 1):
            mx = max(mx, pos[i + 1] - pos[i])
        res = min(res, mx // 2)
    return res


def solution_2670(nums: List[int]) -> List[int]:
    n = len(nums)
    suf = [0] * (n + 1)  # s[n]用于计算最后一个下标的后缀数量
    s = set()
    for i in range(n - 1, 0, -1):
        s.add(nums[i])
        suf[i] = len(s)
    s.clear()
    ans = [0] * n
    for i, x in enumerate(nums):
        s.add(x)
        ans[i] = len(s) - suf[i + 1]
    return ans


def solution_2641(root: Optional[TreeNode]) -> Optional[TreeNode]:
    s = []

    def dfs1(p, level):
        if not p:
            return
        if len(s) < level:
            s.append(p.val)
        else:
            s[level - 1] += p.val
        dfs1(p.left, level + 1)
        dfs1(p.right, level + 1)

    def dfs2(p, level, q):
        if not p:
            return
        lv = p.left.val if p.left else 0
        rv = p.right.val if p.right else 0
        p.val = s[level - 1] - p.val - q
        dfs2(p.left, level + 1, rv)
        dfs2(p.right, level + 1, lv)

    dfs1(root, 1)
    dfs2(root, 1, 0)
    return root


def solution_2641_2(root: Optional[TreeNode]) -> Optional[TreeNode]:
    # BFS
    root.val = 0
    q = [root]
    while q:
        tmp = q
        q = []
        next_level_sum = 0
        for node in tmp:
            if node.left:
                q.append(node.left)
                next_level_sum += node.left.val
            if node.right:
                q.append(node.right)
                next_level_sum += node.right.val

        for node in tmp:
            child_sum = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
            if node.left:
                node.left.val = next_level_sum - child_sum
            if node.right:
                node.right.val = next_level_sum - child_sum
    return root


def solution_2583(root: Optional[TreeNode], k: int) -> int:
    res = []
    q = [root]
    while q:
        tmp = q
        q = []
        vals = []
        for node in tmp:
            vals.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(sum(vals))
    if len(res) >= k:
        res.sort(reverse=True)
        return res[k - 1]
    else:
        return -1


def solution_2867(n: int, edges: List[List[int]]) -> int:
    MX = 10 ** 5 + 1
    is_prime = [True] * MX
    is_prime[1] = False
    for i in range(2, isqrt(MX) + 1):
        if is_prime[i]:
            for j in range(i * i, MX, i):
                is_prime[j] = False
    g = [[] for _ in range(n + 1)]
    for x, y in edges:
        g[y].append(x)
        g[x].append(y)

    def dfs(x, fa):
        nodes.append(x)
        for y in g[x]:
            if y != fa and not is_prime[y]:
                dfs(y, x)

    ans = 0
    size = [0] * (n + 1)
    for x in range(1, n + 1):
        if not is_prime[x]:
            continue
        s = 0
        for y in g[x]:  # 质数 x 把这棵树分成了若干个连通块
            if is_prime[y]:
                continue
            if size[y] == 0:  # 尚未计算过
                nodes = []
                dfs(y, -1)  # 遍历 y 所在连通块，在不经过质数的前提下，统计有多少个非质数
                for z in nodes:
                    size[z] = len(nodes)
            # 这 size[y] 个非质数与之前遍历到的 s 个非质数，两两之间的路径只包含质数 x
            ans += size[y] * s
            s += size[y]
        ans += s  # 从 x 出发的路径
    return ans


def solution_2673(n: int, cost: List[int]) -> int:
    ans = 0
    for i in range(n // 2, 0, -1):
        ans += abs(cost[2 * i - 1] - cost[2 * i])
        cost[i - 1] += max(cost[2 * i - 1], cost[2 * i])
    return ans


def solution_2581(edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
    n = len(edges) + 1
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        g[b].append(a)
    cnt = [0] * n
    fa = [-1] * n

    def dfs1(x, p):
        fa[x] = p
        for y in g[x]:
            if y != p:
                dfs1(y, x)

    dfs1(0, -1)
    guesses_set = set()
    for u, v in guesses:
        guesses_set.add((u, v))
        if fa[v] == u:
            cnt[0] += 1
    ans = 0 if cnt[0] < k else 1

    def dfs2(x, p):
        nonlocal ans
        c = cnt[p]
        if (x, p) in guesses_set:
            c += 1
        if (p, x) in guesses_set:
            c -= 1
        if c >= k:
            ans += 1
        cnt[x] = c
        for y in g[x]:
            if y != p:
                dfs2(y, x)

    for t in g[0]:
        dfs2(t, 0)

    return ans


def solution_2917(nums: List[int], k: int) -> int:
    cnt = defaultdict(int)
    for num in nums:
        cur = 0
        while num > 0:
            cnt[cur] += num & 1
            num = num >> 1
            cur += 1
    ans = 0
    for c in cnt:
        if cnt[c] >= k:
            ans += 1 << c
    return ans


def solution_2575(word: str, m: int) -> List[int]:
    r = 0
    ans = []
    for c in word:
        r += (ord(c) - ord('0'))
        r = r % m
        if r == 0:
            ans.append(1)
        else:
            ans.append(0)
            r = (r * 10) % m
    return ans


def solution_2834(n: int, target: int) -> int:
    mod_num = 10 ** 9 + 7
    mid = target // 2
    sum = 0
    cnt1 = min(mid, n)
    sum = ((cnt1 + 1) * cnt1) // 2
    if mid < n:
        cnt = n - mid
        sum += (target + target + cnt - 1) * cnt // 2
    return sum % mod_num


def solution_2864(s: str) -> str:
    ls = list(s)
    n = len(ls)
    p, q = 0, n - 1
    while q > -1 and ls[q] != '1':
        q -= 1
    if q != n - 1:
        ls[q] = '0'
        ls[-1] = '1'
    else:
        q -= 1
    n = n - 1
    while p < q:
        while p < n and ls[p] != '0':
            p += 1
        while q > -1 and ls[q] != '1':
            q -= 1
        if p < q:
            ls[p], ls[q] = '1', '0'
            p += 1
            while p < n and ls[p] != '0':
                p += 1
            q -= 1
            while q > -1 and ls[q] != '1':
                q -= 1
    return ''.join(ls)


def solution_2789(nums: List[int]) -> int:
    cur = nums[-1]
    mc = cur
    for num in nums[-2::-1]:
        if num > cur:
            mc = max(cur, mc)
            cur = num
        else:
            cur += num
    return max(mc, cur)


def solution_2684(grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    mc = 0

    @cache
    def dfs(i, j) -> int:
        """
        从grid[i][j]出发，移动的最大次数
        """
        if j == n - 1:
            return 0
        ans = 0
        if i > 0 and grid[i][j] < grid[i - 1][j + 1]:
            ans = max(ans, 1 + dfs(i - 1, j + 1))
        if i >= 0 and grid[i][j] < grid[i][j + 1]:
            ans = max(ans, 1 + dfs(i, j + 1))
        if m - 1 > i and grid[i][j] < grid[i + 1][j + 1]:
            ans = max(ans, 1 + dfs(i + 1, j + 1))
        return ans

    for i in range(m):
        mc = max(dfs(i, 0), mc)
    return mc


def solution_2671():
    # data_struct.FrequencyTracker
    ...


def solution_2617(grid: List[List[int]]) -> int:
    # TLE
    m = len(grid)
    n = len(grid[0])
    f = [[-1] * n for _ in range(m)]
    f[m - 1][n - 1] = 0
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            steps = grid[i][j]
            for s in range(1, steps + 1):
                if i + s < m and (f[i][j] < 0 or 0 <= f[i + s][j] < f[i][j]):
                    f[i][j] = f[i + s][j]
            for s in range(1, steps + 1):
                if j + s < n and (f[i][j] < 0 or 0 <= f[i][j + s] < f[i][j]):
                    f[i][j] = f[i][j + s]
            if f[i][j] >= 0:
                f[i][j] += 1
    return f[0][0]


def solution_2617_2(grid: List[List[int]]) -> int:
    """
    单调栈+DP
    单调栈维护最小步数以及对应的下标,单调增
    如果栈顶比当前值大，说明下标靠右的格子反而需要更多步数，因此这个结果不再需要了
    二分查找快速找到对应位置,比该位置靠右的当前格子走不过去，比该位置靠左的用的步数更多
    """
    m, n = len(grid), len(grid[0])
    col_stacks = [[] for _ in range(n)]
    mn = inf
    for i in range(m - 1, -1, -1):
        row_st = []  # 当前行的单调栈
        for j in range(n - 1, -1, -1):
            g = grid[i][j]
            col_st = col_stacks[j]
            mn = inf if i < m - 1 or j < n - 1 else 1  # f[m-1][n-1]=1 其他为inf
            if g:
                # 在这一行上找
                k = bisect.bisect_left(row_st, -(j + g), key=lambda p: p[1])
                if k < len(row_st):
                    mn = row_st[k][0] + 1
                k = bisect.bisect_left(col_st, -(i + g), key=lambda p: p[1])
                if k < len(col_st):
                    mn = min(col_st[k][0] + 1, mn)
            if mn < inf:
                while row_st and mn <= row_st[-1][0]:
                    row_st.pop()
                row_st.append((mn, -j))
                while col_st and mn <= col_st[-1][0]:
                    col_st.pop()
                col_st.append((mn, -i))
    return mn if mn < inf else -1


def solution_2617_3(grid: List[List[int]]) -> int:
    """
    贪心+最小堆
    正向推
    """
    col_heaps = [[] for _ in grid[0]]
    f = inf
    for i, row in enumerate(grid):
        row_h = []
        for j, (g, col_h) in enumerate(zip(row, col_heaps)):
            while row_h and row_h[0][1] < j:  # 无法到j列
                heapq.heappop(row_h)
            while col_h and col_h[0][1] < i:  # 无法到i行
                heapq.heappop(col_h)
            f = inf if i or j else 1
            if row_h:
                f = row_h[0][0] + 1
            if col_h:
                f = min(f, col_h[0][0] + 1)
            if g and f < inf:
                heapq.heappush(row_h, (f, g + j))
                heapq.heappush(col_h, (f, g + i))
    return f if f < inf else -1


def solution_2580(ranges: List[List[int]]) -> int:
    mod_factor = 10 ** 9 + 7
    ranges.sort(key=lambda x: x[0])
    ans = [ranges[0]]
    idx = 0
    curl, curr = ans[idx][0], ans[idx][1]
    for r in ranges[1:]:
        if r[0] <= curr:
            curr = ans[idx][1] = max(curr, r[1])
        else:
            ans.append(r)
            idx += 1
            curl, curr = ans[idx][0], ans[idx][1]
    f = len(ans)
    b = 2
    ans = 1
    while f > 0:
        if f & 1:
            ans = (ans * b) % mod_factor
        b = (b * b) % mod_factor
        f >>= 1
    return ans


def solution_2908(nums: List[int]) -> int:
    n = len(nums)
    pre = [0] * n
    suf = [0] * n
    cur = inf
    for i, x in enumerate(nums):
        if x < cur:
            cur = x
        pre[i] = cur
    cur = inf
    for i in range(n - 1, -1, -1):
        if nums[i] < cur:
            cur = nums[i]
        suf[i] = cur

    ans = inf
    for i in range(1, n - 1):
        if pre[i] < nums[i] > suf[i]:
            ans = min(ans, pre[i] + suf[i] + nums[i])
    return ans if ans < inf else -1


def solution_2952(coins: List[int], target: int) -> int:
    coins.sort()
    x = 0
    cnt = 0
    for coin in coins:
        while coin > x + 1:
            cnt += 1
            # add x+1
            x = 2 * x + 1
        x = x + coin
        if x >= target:
            return cnt
    while x < target:
        cnt += 1
        x = 2 * x + 1
    return cnt


def solution_2810(s: str) -> str:
    ans = []
    for c in s:
        if c == 'i':
            ans.reverse()
        else:
            ans.append(c)
    return ''.join(ans)


def solution_2810_2(s: str) -> str:
    # 双端队列
    q = deque()
    tail = True
    for c in s:
        if c == 'i':
            tail = not tail
        elif tail:
            q.append(c)
        else:
            q.appendleft(c)
    return ''.join(q if tail else reversed(q))


def solution_2549(n: int) -> int:
    return n - 1 if n > 1 else n


def solution_2642():
    # data_struct.Graph
    ...


def solution_2529(nums: List[int]) -> int:
    left, right = -1, len(nums)
    while left + 1 < right:
        mid = (left + right) // 2
        if nums[mid] >= 0:
            right = mid
        else:
            left = mid
    # [0,left] <0
    neg = left + 1
    left, right = -1, len(nums)
    while left + 1 < right:
        mid = (left + right) // 2
        if nums[mid] > 0:
            right = mid
        else:
            left = mid
    # [right,-1] >0
    pos = len(nums) - right
    return max(neg, pos)


def solution_2923(grid: List[List[int]]) -> int:
    cnt = {x: 0 for x in range(len(grid))}
    for i, row in enumerate(grid):
        for j, c in enumerate(row):
            if c == 1:
                cnt[j] += 1
    for i in cnt:
        if cnt[i] == 0:
            return i


def solution_2923_2(grid: List[List[int]]) -> int:
    ans = 0
    for i, row in enumerate(grid):
        if row[ans]:
            ans = i
    return ans


def solution_2924(n: int, edges: List[List[int]]) -> int:
    g = [[] for _ in range(n)]
    for x, y in edges:
        g[x].append(y)

    pa = [-1] * n
    visited = [False] * n

    def dfs(x, fa):
        if pa[x] == -1:
            pa[x] = fa
        for y in g[x]:
            if (not visited[y] or pa[y] == -1) and y != fa:
                visited[y] = True
                dfs(y, x)

    for i in range(n):
        if not visited[i] or pa[i] == -1:
            visited[i] = True
            dfs(i, -1)
    cnt = 0
    ans = 0
    for i, x in enumerate(pa):
        if x == -1:
            cnt += 1
            ans = i
        if cnt >= 2:
            return -1
    return ans


def solution_2924_2(n: int, edges: List[List[int]]) -> int:
    lose = [False] * n
    for _, y in edges:
        lose[y] = True

    ans = -1
    for i, x in enumerate(lose):
        if x:
            continue
        if ans != -1:
            return -1
        ans = i
    return ans


def solution_2739(mainTank: int, additionalTank: int) -> int:
    ans = 0
    cnt = 0
    while mainTank > 0:
        mainTank -= 1
        ans += 10
        cnt += 1
        if cnt == 5 and additionalTank > 0:
            mainTank += 1
            cnt = 0
            additionalTank -= 1
    return ans


def solution_2639(grid: List[List[int]]) -> List[int]:
    n = len(grid)
    m = len(grid[0])
    ans = [0] * m
    for i in range(n):
        for j in range(m):
            ans[j] = max(ans[j], len(str(grid[i][j])))
    return ans


def solution_2798(hours: List[int], target: int) -> int:
    ans = 0
    for hour in hours:
        if hour >= target:
            ans += 1
    return ans


def solution_2960(batteryPercentages: List[int]) -> int:
    ans = 0
    for x in batteryPercentages:
        if x > ans:
            ans += 1
    return ans


def solution_2589(tasks: List[List[int]]) -> int:
    tasks.sort(key=lambda t: t[1])
    # 标记哪些点在运行
    run = [False] * (tasks[-1][1] + 1)
    for start, end, d in tasks:
        d -= sum(run[start: end + 1])  # 去掉运行中的时间点
        if d <= 0:  # 该任务已完成
            continue
        # 该任务尚未完成，从后往前找没有运行的时间点
        for i in range(end, start - 1, -1):
            if run[i]:  # 已运行
                continue
            run[i] = True  # 运行
            d -= 1
            if d == 0:
                break
    return sum(run)


def solution_2589_2(tasks: List[List[int]]) -> int:
    tasks.sort(key=lambda t: t[1])
    # 栈中保存闭区间左右端点，栈底到栈顶的区间长度的和
    st = [(-2, -2, 0)]  # 哨兵，保证不和任何区间相交
    for start, end, d in tasks:
        _, r, s = st[bisect.bisect_left(st, (start,)) - 1]
        d -= st[-1][2] - s  # 去掉运行中的时间点
        if start <= r:  # start 在区间 st[i] 内
            d -= r - start + 1  # 去掉运行中的时间点
        if d <= 0:
            continue
        while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀
            l, r, _ = st.pop()
            d += r - l + 1  # 合并区间
        st.append((end - d + 1, end, st[-1][2] + d))
    return st[-1][2]


def solution_2644(nums: List[int], divisors: List[int]) -> int:
    divisors.sort()
    ans = divisors[0]
    mx = 0
    for divisor in divisors:
        cur = 0
        for num in nums:
            if num % divisor == 0:
                cur += 1
        if cur > mx:
            mx = cur
            ans = divisor
    return ans


def solution_2644_2(nums: List[int], divisors: List[int]) -> int:
    nums.sort(reverse=True)
    dup = sum(1 for x, y in itertools.pairwise(nums) if x == y)
    divisors.sort()
    mx, ans = -1, 0
    for divisor in divisors:
        # 就算全是d的倍数 也无法超过mx
        if (mx - dup + 1) * divisor > nums[0]:
            break
        cnt = 0
        for num in nums:
            if num < divisor:
                break
            if num % divisor == 0:
                cnt += 1
        if cnt > mx:
            mx, ans = cnt, divisor
    return ans


def solution_2769(num: int, t: int) -> int:
    return num + t * 2


def solution_2831(nums: List[int], k: int) -> int:
    pos_lists = defaultdict(list)
    for i, x in enumerate(nums):
        pos_lists[x].append(i)
    ans = 0
    for pos in pos_lists.values():
        if len(pos) < ans:
            continue
        left = 0
        for right, p in enumerate(pos):
            while (p - pos[left] + 1) - (right - left + 1) > k:
                left += 1
            ans = max(ans, right - left + 1)
    return ans


def solution_2903(nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
    for i in range(len(nums) - indexDifference):
        for j in range(i + indexDifference, len(nums)):
            if abs(nums[i] - nums[j]) >= valueDifference:
                return [i, j]
    return [-1, -1]


def solution_2951(mountain: List[int]) -> List[int]:
    n = len(mountain)
    ans = []
    for i in range(1, n - 1):
        if mountain[i] > mountain[i - 1] and mountain[i] > mountain[i + 1]:
            ans.append(i)
    return ans


def solution_2981(s: str) -> int:
    f = defaultdict(list)
    start = 0
    for i in range(len(s)):
        if i + 1 != len(s) and s[i] == s[i + 1]:
            continue
        else:
            f[s[start]].append(i - start + 1)
            start = i + 1
    ans = -1
    for c in f:
        tmp = f[c]
        tmp.sort(reverse=True)
        tmp.extend([0, 0])
        ans = max(ans, tmp[0] - 2, min(tmp[0] - 1, tmp[1]), tmp[2])
    return ans if ans else -1


def solution_2982(s: str) -> int:
    return solution_2981(s)


def solution_2965(grid: List[List[int]]) -> List[int]:
    m = len(grid) ** 2
    d1 = sum(x for row in grid for x in row) - m * (m + 1) // 2
    d2 = sum(x * x for row in grid for x in row) - m * (m + 1) * (m * 2 + 1) // 6
    return [(d2 // d1 + d1) // 2, (d2 // d1 - d1) // 2]


def solution_2928(n: int, limit: int) -> int:
    def c2(n: int) -> int:
        return n * (n - 1) // 2 if n > 1 else 0

    return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)


def solution_2938(s: str) -> int:
    ans = cnt1 = 0
    for c in s:
        if c == '1':
            cnt1 += 1
        else:
            ans += cnt1
    return ans


def solution_2595(n: int) -> List[int]:
    # ans = [0,0]
    # for i in range(n.bit_length()):
    #     if (n >> i) & 1:
    #         ans[i%2]+=1
    # return ans
    MASK = 0x5555
    return [(n & MASK).bit_count(), (n & (MASK >> 1)).bit_count()]


def solution_2779(nums: List[int], k: int) -> int:
    nums.sort()
    n = len(nums)
    ans = 0
    for i in range(n):
        if n - i <= ans:
            break
        ans = max(ans, bisect.bisect_right(nums, nums[i] + 2 * k) - i)
    return ans


def solution_2806(purchaseAmount: int) -> int:
    a = 10 * (purchaseAmount // 10)
    b = a + 10
    if purchaseAmount - a < b - purchaseAmount:
        x = a
    else:
        x = b
    return 100 - x


def solution_2813(items: List[List[int]], k: int) -> int:
    items.sort(key=lambda x: x[0], reverse=True)
    ans = total_profit = 0
    vis = set()
    dup = []
    for i, (profit, category) in enumerate(items):
        if i < k:
            total_profit += profit
            if category not in vis:
                vis.add(category)
            else:
                dup.append(profit)
        elif dup and category not in vis:
            vis.add(category)
            total_profit += profit - dup.pop()
        ans = max(ans, total_profit + len(vis) * len(vis))
    return ans


def solution_2786(nums: List[int], x: int) -> int:
    @cache
    def dfs(i, even):
        if i == len(nums):
            return 0
        if nums[i] % 2 == even:
            return dfs(i + 1, even) + nums[i]
        else:
            return max(dfs(i + 1, even), dfs(i + 1, even ^ 1) + nums[i] - x)

    return dfs(1, nums[0] % 2) + nums[0]


def solution_2713(mat: List[List[int]]) -> int:
    g = defaultdict(list)
    for i, row in enumerate(mat):
        for j, x in enumerate(row):
            g[x].append((i, j))
    row_max = [0] * len(mat)
    col_max = [0] * len(mat[0])
    for _, pos in sorted(g.items(), key=lambda p: p[0]):
        mx = [max(row_max[i], col_max[j]) + 1 for i, j in pos]
        for (i, j), f in zip(pos, mx):
            row_max[i] = max(row_max[i], f)
            col_max[j] = max(col_max[j], f)
    return max(row_max)


def solution_2748(nums: List[int]) -> int:
    n = len(nums)
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            x, y = nums[i], nums[j]
            while x >= 10:
                x //= 10
            y = y % 10
            if math.gcd(x, y) == 1:
                print(x, y)
                ans += 1
    return ans


def solution_2980(nums: List[int]) -> bool:
    cnt = 0
    for n in nums:
        cnt += 1 ^ (n & 1)
        if cnt == 2:
            return True
    return False


def solution_2871(nums: List[int]) -> int:
    ans = 0
    t = -1
    for x in nums:
        t = t & x
        if t == 0:
            ans += 1
            t = -1
    return max(ans, 1)


def solution_2663(s: str, k: int) -> str:
    a = ord('a')
    k += a
    s = list(map(ord, s))
    n = len(s)
    i = n - 1
    s[i] += 1
    while i < n:
        if s[i] == k:
            if i == 0:
                return ""
            s[i] = a
            i -= 1
            s[i] += 1
        elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:
            s[i] += 1  # 如果 s[i] 和左侧的字符形成回文串，就继续增加 s[i]
        else:
            i += 1  # 反过来检查后面是否有回文串
    return ''.join(map(chr, s))


def solution_2732(grid: List[List[int]]) -> List[int]:
    n = len(grid[0])
    f = [-1] * (1 << n)
    for i, row in enumerate(grid):
        mask = 0
        for j, x in enumerate(row):
            mask |= x << j
        if mask == 0:
            return [i]
        f[mask] = i
    u = (1 << n) - 1
    for s in range(1, u):
        for b in range(n):
            if (s >> b) & 1 == 0:  # 如果合法 在预处理时已经return
                continue
            i = f[s] = max(f[s], f[s ^ (1 << b)])  # 修正-1
            if i < 0:
                continue
            j = f[u ^ s]
            if j >= 0:
                return sorted((i, j))
    return []


def solution_2741(nums: List[int]) -> int:
    MOD = 10 ** 9 + 7
    n = len(nums)

    @cache
    def dfs(last, S):
        if S == (1 << n) - 1:
            return 1
        res = 0
        for i in range(n):
            if (S >> i) & 1:
                continue
            x = nums[i]
            if x % last == 0 or last % x == 0:
                res = (res + dfs(x, S | (1 << i))) % MOD
        return res

    return dfs(1, 0)


def solution_2734(s: str) -> str:
    n = len(s)
    left = 0
    while left < n and s[left] == 'a':
        left += 1
    if left >= n:
        return 'a' * (n - 1) + 'z'
    right = left
    while right < n and s[right] != 'a':
        right += 1
    ans = list(s[left:right])
    for i in range(len(ans)):
        ans[i] = chr(ord(ans[i]) - 1)
    return s[:left] + "".join(ans) + s[right:]


def solution_2742(cost: List[int], time: List[int]) -> int:
    @cache
    def dfs(i, cnt):
        if cnt >= len(cost):
            return 0
        if i == len(cost):
            return inf
        res1 = dfs(i + 1, cnt)
        res2 = cost[i] + dfs(i + 1, cnt + 1 + time[i])
        return res1 if res1 < res2 else res2

    return dfs(0, 0)


def solution_2710(num: str) -> str:
    for i in range(len(num) - 1, -1, -1):
        if num[i] != '0':
            return num[:i + 1]


def solution_2680(nums: List[int], k: int) -> int:
    n = len(nums)
    pre = [0] * (n + 1)
    suf = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] | nums[i]
    for i in range(n - 1, -1, -1):
        suf[i] = suf[i + 1] | nums[i]
    ans = 0
    for i in range(n):
        x = nums[i]
        other = pre[i] | suf[i + 1]
        ans = max(ans, other | (x << k))
    return ans


def solution_2735(nums: List[int], x: int) -> int:
    n = len(nums)
    s = list(range(0, n * x, x))  # s[k] 统计操作 k 次的总成本
    for i, mn in enumerate(nums):  # 子数组左端点
        for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）
            mn = min(mn, nums[j % n])  # 维护从 nums[i] 到 nums[j] 的最小值
            s[j - i] += mn  # 累加操作 j-i 次的花费
    return min(s)


def solution_2740(nums: List[int]) -> int:
    nums.sort()
    ans = inf
    for x, y in itertools.pairwise(nums):
        ans = min(y - x, ans)
    return ans


def solution_2580_2(ranges: List[List[int]]) -> int:
    mymax = lambda a, b: a if a > b else b
    ranges.sort()
    cnt = 0
    e = -1
    for s1, e1 in ranges:
        if s1 > e:
            cnt += 1
        e = mymax(e, e1)
    return (1 << cnt) % (10 ** 9 + 7)


def solution_2844(num: str) -> int:
    n = len(num)

    # ans = n - num.count('0')
    # for i in range(n-1,-1,-1):
    #     for j in range(i-1,-1,-1):
    #         tmp = int(num[j]+num[i])
    #         if not tmp % 25:
    #             ans = min(ans, n - j - 2)
    # return ans
    # def f(tail):
    #     i = num.rfind(tail[1])
    #     if i <= 0:
    #         return n
    #     i = num.rfind(tail[0], 0, i)
    #     return n if i < 0 else n - i - 2

    # return min(n - ("0" in num), f("00"), f("25"), f("50"), f("75"))
    f0 = f5 = False
    for i in range(n - 1, -1, -1):
        c = num[i]
        if f0 and c in "05" or f5 and c in "27":
            return n - i - 2
        if c == '0':
            f0 = True
        elif c == '5':
            f5 = True
    return n - f0


def solution_2799(nums: List[int]) -> int:
    m = len(set(nums))
    cnt = Counter()
    ans = left = 0
    for v in nums:
        cnt[v] += 1
        while len(cnt) == m:
            x = nums[left]
            cnt[x] -= 1
            if cnt[x] == 0:
                del cnt[x]
            left += 1
        ans += left  # 子数组左端点 < left 的都是合法的 此时右端点是v对应的下标
    return ans


def solution_2568(nums: List[int]) -> int:
    mask = 0
    for x in nums:
        if x & (x - 1) == 0:
            mask |= x
    mask = ~mask
    return mask & -mask


def solution_2766(nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:
    stones = set(nums)
    for i in range(len(moveFrom)):
        stones.remove(moveFrom[i])
        stones.add(moveTo[i])
    return sorted(list(stones))


def solution_2571(n: int) -> int:
    # m = n.bit_length()
    # left, right= m , m-1
    # ans = 0
    # while right > - 1:
    #     if not (n >> right) & 1:
    #         ans += min(left-right,2)
    #         left = right - 1
    #         while left > - 1 and  not (n >> left) & 1:
    #             left -= 1
    #         right = left
    #     right -= 1
    # return ans + min(left-right,2)
    ans = 1
    while n & (n - 1):
        lb = n & (-n)
        if n & (lb << 1):
            n += lb  # 多个连续 1 用加法
        else:
            n -= lb
        ans += 1
    return ans


def solution_2546(s: str, target: str) -> bool:
    return ('1' in s) == ('1' in target)


def solution_2850(grid: List[List[int]]) -> int:
    from_ = []
    to = []
    for i, row in enumerate(grid):
        for j, cnt in enumerate(row):
            if cnt > 1:
                from_.extend([(i, j)] * (cnt - 1))
            elif cnt == 0:
                to.append((i, j))
    ans = inf
    for from2 in itertools.permutations(from_):
        total = 0
        for (x1, y1), (x2, y2) in zip(from2, to):
            total += abs(x1 - x2) + abs(y1 - y2)
        ans = min(ans, total)
    return ans


def solution_2959(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
    mymin = lambda a, b: a if a < b else b
    g = [[inf] * n for _ in range(n)]
    for i in range(n):
        g[i][i] = 0
    for x, y, wt in roads:
        g[x][y] = min(g[x][y], wt)
        g[y][x] = min(g[y][x], wt)
    ans = 1  # 空集
    f = [[[inf] * n for _ in range(n)] for _ in range(1 << n)]
    f[0] = g  # 中间节点为空集
    for s in range(1, 1 << n):
        k = s.bit_length() - 1  # 最大元素，实际可以取任意元素，仅方便计算
        t = s ^ (1 << k)  # 取子集
        ok = 1
        for i in range(n):
            for j in range(n):
                f[s][i][j] = mymin(f[t][i][j], f[t][i][k] + f[t][k][j])
                if ok and s >> i & 1 and s >> j & 1 and f[s][i][j] > maxDistance:
                    ok = 0
        ans += ok
    return ans


def solution_2957(word: str) -> int:
    last = 0
    ans = 0
    for i in range(1, len(word)):
        x, y = ord(word[i]), ord(word[i - 1])
        if -1 <= x - y <= 1:
            continue
        else:
            length = i - last
            last = i
            ans += length // 2
    ans += (len(word) - last) // 2
    return ans


def solution_2956(nums1: List[int], nums2: List[int]) -> List[int]:
    return [sum(1 if x in set(nums2) else 0 for x in nums1), sum(1 if x in set(nums1) else 0 for x in nums2)]


def solution_2857(coordinates: List[List[int]], k: int) -> int:
    ans = 0
    cnt = Counter()
    for x, y in coordinates:
        for i in range(k + 1):
            ans += cnt[x ^ i, y ^ (k - i)]  # tuple 的括号可以省略
        cnt[x, y] += 1  # tuple 的括号可以省略
    return ans


def solution_2974(nums: List[int]) -> List[int]:
    nums.sort()
    for i in range(0, len(nums), 2):
        nums[i], nums[i + 1] = nums[i + 1], nums[i]
    return nums


def solution_2564(s: str, queries: List[List[int]]) -> List[List[int]]:
    n, m = len(s), {}
    if (i := s.find('0')) >= 0:
        m[0] = (i, i)
    for l, c in enumerate(s):
        if c == '0': continue
        x = 0
        for r in range(l, min(l + 30, n)):
            x = (x << 1) | (ord(s[r]) & 1)
            if x not in m:
                m[x] = (l, r)
    not_found = (-1, -1)
    return [list(m.get(x ^ y, not_found)) for x, y in queries]


def solution_2972(a: List[int]) -> int:
    n = len(a)
    i = 0
    while i < n - 1 and a[i] < a[i + 1]:
        i += 1
    if i == n - 1:  # 每个非空子数组都可以移除
        return n * (n + 1) // 2

    ans = i + 2  # 不保留后缀的情况，一共 i+2 个
    # 枚举保留的后缀为 a[j:]
    j = n - 1
    while j == n - 1 or a[j] < a[j + 1]:
        while i >= 0 and a[i] >= a[j]:
            i -= 1
        # 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个
        ans += i + 2
        j -= 1
    return ans


def solution_2588(nums: List[int]) -> int:
    s = ans = 0
    cnt = Counter()
    cnt[0] = 1
    for x in nums:
        s ^= x
        ans += cnt[s]
        cnt[s] += 1
    return ans


def solution_2317(nums: List[int]) -> int:
    return reduce(or_, nums)


def solution_2527(nums: List[int]) -> int:
    return reduce(xor, nums)


def solution_2970(nums: List[int]) -> int:
    def isInc(x):
        return all(x[i] < x[i + 1] for i in range(len(x) - 1))

    n = len(nums)
    cnt = 0
    for i in range(n):
        for j in range(i, n):
            tmp = nums[:i] + nums[j + 1:]
            if isInc(tmp):
                cnt += 1
    return cnt


def solution_2607(arr: List[int], k: int) -> int:
    n = len(arr)
    t = math.gcd(n, k)
    ans = 0
    for i in range(t):
        b = sorted(arr[i::t])
        x = b[len(b) // 2]
        ans += sum(abs(c - x) for c in b)
    return ans


def solution_2997(nums: List[int], k: int) -> int:
    s = 0
    for x in nums:
        s ^= x
    t = s ^ k
    ans = 0
    while t > 0:
        ans += 1
        t &= t - 1
    return ans


def solution_2683(derived: List[int]) -> bool:
    return reduce(xor, derived) == 0


def solution_2433(pref: List[int]) -> List[int]:
    ans = [0] * len(pref)
    ans[0] = pref[0]
    for i in range(1, len(pref)):
        ans[i] = pref[i - 1] ^ pref[i]
    return ans


def solution_2967(nums: List[int]) -> int:
    pal = []
    base = 1
    while base <= 10000:
        for i in range(base, base * 10):
            x = i
            t = i // 10
            while t:
                x = x * 10 + t % 10
                t //= 10
            pal.append(x)
        if base <= 1000:
            for i in range(base, base * 10):
                x = t = i
                while t:
                    x = x * 10 + t % 10
                    t //= 10
                pal.append(x)
        base *= 10
    pal.append(1_000_000_001)

    nums.sort()

    def cost(i: int) -> int:
        target = pal[i]
        return sum(abs(x - target) for x in nums)

    n = len(nums)
    i = bisect_left(pal, nums[(n - 1) // 2])
    if pal[i] <= nums[n // 2]:
        return cost(i)
    return min(cost(i - 1), cost(i))


def solution_2961(variables: List[List[int]], target: int) -> List[int]:
    def mypow(x, y, mod_factor):
        m = y.bit_length()
        res = 1
        for i in range(m):
            t = (y >> i) & 1
            if t:
                res = res * x % mod_factor
            x = (x * x) % mod_factor
        return res

    ans = []
    for i, (a, b, c, m) in enumerate(variables):
        if mypow(mypow(a, b, 10), c, m) == target:
            ans.append(i)
    return ans


def solution_2940(heights: List[int], queries: List[List[int]]) -> List[int]:
    ans = [-1] * len(queries)
    qs = [[] for _ in heights]
    for i, (a, b) in enumerate(queries):
        if a > b:
            a, b = b, a
        if a == b or heights[a] < heights[b]:
            ans[i] = b  # 最优解是b
        else:
            qs[b].append((heights[a], i))
    h = []
    for i, x in enumerate(heights):
        while h and h[0][0] < x:
            ans[heappop(h)[1]] = i
        for q in qs[i]:
            heappush(h, q)
    return ans


def solution_2708(nums: List[int]) -> int:
    mn = mx = nums[0]
    for x in nums[1:]:
        mn, mx = min(mn, x, mn * x, mx * x), max(mx, x, mn * x, mx * x)
    return mx


def solution_2860(nums: List[int]) -> int:
    nums.sort()
    ans = 0 if nums[0] == 0 else 1
    for i in range(len(nums)):
        if i == len(nums) - 1:
            ans += 1
        else:
            x, y = nums[i], nums[i + 1]
            if x < i + 1 < y:
                ans += 1
    return ans


def solution_2552(nums: List[int]) -> int:
    n = len(nums)
    great = [0] * n
    great[-1] = [0] * (n + 1)
    for k in range(n - 2, 1, -1):
        great[k] = great[k + 1][:]
        for x in range(1, nums[k + 1]):
            great[k][x] += 1
    ans = 0
    less = [0] * (n + 1)
    for j in range(1, n - 1):
        for x in range(nums[j - 1] + 1, n + 1):
            less[x] += 1
        for k in range(j + 1, n - 1):
            if nums[j] > nums[k]:
                ans += less[nums[k]] * great[k][nums[j]]
    return ans


def solution_2555(prizePositions: List[int], k: int) -> int:
    n = len(prizePositions)
    if k * 2 + 1 >= prizePositions[-1] - prizePositions[0]:
        return n
    ans = left = 0
    mx = [0] * (n + 1)
    for right, p in enumerate(prizePositions):
        while p - prizePositions[left] > k:
            left += 1
        ans = max(ans, mx[left] + right - left + 1)
        mx[right + 1] = max(mx[right], right - left + 1)
    return ans


def solution_2576(nums: List[int]) -> int:
    nums.sort()
    n = len(nums)

    def check(k):
        lo = 0
        hi = n - k
        for i in range(k):
            x, y = nums[lo], nums[hi]
            if y < 2 * x:
                return True
            lo += 1
            hi += 1
        return False

    return (bisect_left(range(n // 2 + 1), True, key=check) - 1) * 2


def solution_2576_2(nums: List[int]) -> int:
    nums.sort()
    i = 0
    for x in nums[(len(nums) + 1) // 2:]:
        if nums[i] * 2 <= x:
            i += 1
    return i * 2


def solution_2848(nums: List[List[int]]) -> int:
    nums.sort(key=lambda x: x[0])
    left = nums[0][0]
    right = nums[0][1]
    ans = 0
    for x, y in nums[1:]:
        if x <= right:
            right = max(y, right)
        else:
            ans += right - left + 1
            left, right = x, y
    ans += right - left + 1
    return ans


def solution_2848_2(nums: List[List[int]]) -> int:
    mx_end = max(end for _, end in nums)
    diff = [0] * (mx_end + 2)
    for start, end in nums:
        diff[start] += 1
        diff[end + 1] -= 1
    return sum(s > 0 for s in itertools.accumulate(diff))


def solution_2535(nums: List[int]) -> int:
    sum1 = sum(nums)
    sum2 = 0
    for x in nums:
        while x > 0:
            x, y = divmod(x, 10)
            sum2 += y
    return abs(sum1 - sum2)


def solution_2541(nums1: List[int], nums2: List[int], k: int) -> int:
    add = 0
    minus = 0
    if k == 0:
        return 0 if all(nums1[i] == nums2[i] for i in range(len(nums1))) else -1
    for i in range(len(nums1)):
        x = nums1[i] - nums2[i]
        if x % k != 0:
            return -1
        if x > 0:
            add += x // k
        else:
            minus -= x // k
    if add == minus:
        return add
    return -1


def solution_2516(s: str, k: int) -> int:
    cnt = Counter(s)
    if any(cnt[c] < k for c in 'abc'):
        return -1

    mx = left = 0
    for right, c in enumerate(s):
        cnt[c] -= 1
        while cnt[c] < k:
            cnt[s[left]] += 1
            left += 1
        mx = max(mx, right - left + 1)
    return len(s) - mx


def solution_2825(str1: str, str2: str) -> bool:
    i = j = 0
    while i < len(str2) and j < len(str1):
        c = ord(str2[i])
        x = (c - ord(str1[j])) % 26
        if x == 0 or x == 1:
            i += 1
        j += 1
    return i == len(str2)
